/**
 * 
 */
package combinatorics.passed;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

/**
 * @author xyyi
 *
 */
public class Subsets {

	/**
	Given a set of distinct integers, S, return all possible subsets.

	Note:

	Elements in a subset must be in non-descending order.
	The solution set must not contain duplicate subsets.
	For example,
	If S = [1,2,3], a solution is:

	[
	[3],
	[1],
	[2],
	[1,2,3],
	[1,3],
	[2,3],
	[1,2],
	[]
	]
	 */
	public ArrayList<ArrayList<Integer>> subsets(int[] S) {
		// Start typing your Java solution below
		// DO NOT write main() function
		ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
		if (S == null)
			return list;
		ArrayList<Integer> buffer = new ArrayList<Integer>();
		subsets(S, buffer, list, 0);
		return list;
	}

	public void subsets(int[] S, ArrayList<Integer> buffer,
			ArrayList<ArrayList<Integer>> list, int index) {
		if (index == S.length) {
			ArrayList<Integer> arr = new ArrayList<Integer>(buffer);
			Collections.sort(arr);
			list.add(arr);
		} else {
			buffer.add(S[index]);
			subsets(S, buffer, list, index + 1);
			buffer.remove(buffer.size() - 1);
			subsets(S, buffer, list, index + 1);
		}
	}

	public ArrayList<ArrayList<Integer>> subsets1(int[] S) {
		ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
		if (S != null) {
			ArrayList<Integer> buffer = new ArrayList<Integer>();
			list.add(new ArrayList<Integer>(buffer));
			Arrays.sort(S);
			subsets1(S, buffer, list, 0);
		}
		return list;
	}

	// best for interview
	public void subsets1(int[] S, ArrayList<Integer> buffer,
			ArrayList<ArrayList<Integer>> list, int index) {
		for (int i = index; i < S.length; i++) {
			buffer.add(S[i]);
			list.add(new ArrayList<Integer>(buffer));
			subsets1(S, buffer, list, i + 1);
			buffer.remove(buffer.size() - 1);
		}
	}

	public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
		ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
		if (num == null)
			return list;
		ArrayList<Integer> buffer = new ArrayList<Integer>();
		list.add(new ArrayList<Integer>(buffer));
		Arrays.sort(num);
		subsetsWithDup(num, buffer, list, 0);
		return list;
	}

	public void subsetsWithDup(int[] num, ArrayList<Integer> buffer,
			ArrayList<ArrayList<Integer>> list, int index) {

		for (int i = index; i < num.length; i++) {
			buffer.add(num[i]);
			list.add(new ArrayList<Integer>(buffer));
			//if (i < num.length - 1) {
			subsetsWithDup(num, buffer, list, i + 1);
			//}
			buffer.remove(buffer.size() - 1);
			while (i < num.length - 1 && num[i] == num[i + 1])
				i++;
		}
	}

	/**
	 * 
	 */
	public Subsets() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Subsets subSet = new Subsets();
		int[] S = new int[] { 1, 2, 3 };
		ArrayList<ArrayList<Integer>> lists = subSet.subsets1(S);
		for (ArrayList<Integer> list : lists) {
			for (int i : list) {
				System.out.printf("%d,", i);
			}
			System.out.println();
		}

	}

}
